package com.lcy.algorithm.huawei;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 题目描述∶在某个项目中n个任务.
 * 每个任务输入为s e, 其中s表示开始的天数,e表示结束的天数
 * 你可以在s <= day <= e 中的任意一天处理该任务。
 * 每天只能处理一个任务。
 * 求你可以处理的最大任务数
 *
 * 输入描述∶
 * 第一行为任务数量n ,1<= n <= 100000。后面n行表示各个任务的开始时间和终止时间，
 * 后面每一行表示每个任务的处理时间范围
 * 输出为一个整数，表示可以处理的最大任务数。
 *
 * 示例1
 * 输入∶
 * 3
 * 1 1
 * 1 2
 * 1 3
 * 输出∶3
 * 说明︰第一天处理任务1，第二天处理任务2，第三天处理任务3。
 */
public class 任务处理 {
    static class Range {
        int start;
        int end;

        public Range(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static void main(String[] args) {
//        method1();
        method2();
    }


    /**
     * 性能一般,容易理解
     */
    public static void method1() {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        // 结束时间越大（越晚）优先级越高，结束时间相同时，开始时间越大（越晚）优先级越高
        // 每次选出一个任务后，需要重新排序，因此考虑使用优先队列（底层是堆）来提高效率
        PriorityQueue<Range> pq =
                new PriorityQueue<>((a, b) -> a.end != b.end ? b.end - a.end : b.start - a.start);

        for (int i = 0; i < n; i++) {
            pq.offer(new Range(sc.nextInt(), sc.nextInt()));
        }

        // 记录最大任务数
        int count = 0;

        // 记录上一个任务的执行时刻
        int last_end = Integer.MAX_VALUE;

        while (pq.size() > 0) {
            Range range = pq.poll();

            if (range.end < last_end) {
                // 当前任务结束时刻end < 上个任务结束时刻last_end，则当前任务选择在end时刻执行
                last_end = range.end;
                count++;
            } else if (last_end > range.start) {
                // 当前任务结束时刻end ≥ 上个任务结束时刻last_end，则更新当前任务的结束时间为last_end-1，后重新加入优先队列排队
                // 同时注意range新的结束时间last_end - 1不能小于range.start，否则该任务无法执行
                range.end = last_end - 1;
                pq.offer(range);
            }
        }

        System.out.println(count);
    }


    /**
     * 性能较高,不需要整个重新排序，因为是一遍添加优先队列，一边执行的
     */
    public static void method2() {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[][] ranges = new int[n][2];
        for (int i = 0; i < n; i++) {
            ranges[i][0] = sc.nextInt();
            ranges[i][1] = sc.nextInt();
        }

        // 将所有任务按照结束时间降序
        Arrays.sort(ranges, (a, b) -> b[1] - a[1]);

        // 优先队列中记录的是任务的开始时间，并且开始时间越大，优先级越高
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

        // 优先队列中记录的是结束时间相同的任务的开始时间，pq_end就是优先队列中任务的相同结束时间
//        int pq_end = Integer.MAX_VALUE;
        //重任务中选出结束时间最长的值
        int pq_end = ranges[0][1];

        // 最大任务数
        int count = 0;
        // 当前任务的开始和结束时间
        int start = ranges[0][0];
        int end = ranges[0][1];

        //一边将任务加入优先队列，一边处理任务
        for (int[] range : ranges) {
            start = range[0];
            end = range[1];

            // 如果当前任务的结束时间 小于 优先队列中记录的任务的结束时间，则两个结束时间之间的间隔时间段，可以处理一些紧急任务
            while (pq.size() > 0 && end < pq_end) {
                // 这里的紧急任务即指时间短的任务，即开始时间比较大的任务
                if (pq.poll() <= pq_end) {
                    // 如果紧急任务的开始时间未超过其结束时间，则可以执行
                    count++;
                    pq_end--; // 一个时刻只执行一个任务
                }
            }

            // 间隔时间消耗完后，优先队列中的任务的结束时间全部更新为当前任务的结束时间
            pq.add(start);
            pq_end = end;
        }

        // 处理没有执行完的任务
        while (pq.size() > 0) {
            if (pq.poll() <= pq_end) {
                count++;
                pq_end--;
            }
        }

        System.out.println(count);
    }
}
